%%%-------------------------------------------------------------------
%%% File    : p38.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% Take the number 192 and multiply it by each of 1, 2, and 3:
%%%
%%%    192 * 1 = 192
%%%    192 * 2 = 384
%%%    192 * 3 = 576
%%%
%%% By concatenating each product we get the 1 to 9 pandigital, 
%%% 192384576. 
%%% We will call 192384576 the concatenated product of 192 and (1,2,3)
%%%
%%% The same can be achieved by starting with 9 and multiplying by 
%%% 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the 
%%% concatenated product of 9 and (1,2,3,4,5).
%%%
%%% What is the largest 1 to 9 pandigital 9-digit number that can be 
%%% formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?
%%%
%%%
%%% Created : 29 Dec 2008
%%%-------------------------------------------------------------------
-module(p38).

%% API
-compile(export_all).

%The largest number with concatenated product with (1,2) of 9 digits:
%9999 -> 999919998
%Starting with that generate the concatenated products and check if 
%they are pandigital, returning the largest found.
    
%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: 
%% Description:
%%--------------------------------------------------------------------
solution() ->
    step(9999, 0).

%%====================================================================
%% Internal functions
%%====================================================================
%iterate down until a solution is found
step(1, Max) -> Max;
step(N, Max) ->
    Conc = concatenated_product(N),
    NewMax = case Conc =/= null andalso Conc > Max andalso is_pandigital(Conc) of
                 true ->
                     Conc;
                 _ -> 
                     Max
             end,
    step(N - 1, NewMax).

%Calculate the concatenated product of N with less than 10 digits
concatenated_product(N) ->
    concatenated_product(N, 2, 987654321, N).

concatenated_product(_, 10, _, Acc) ->
    Acc;
concatenated_product(N, I, Max, Acc) ->
    Prod = N*I,
    Pow10 = pow10(Prod, 1),
    NewAcc = Acc*Pow10*10 + Prod,
    case NewAcc > Max of
        true when I =:= 2->
            null;
        true -> Acc;
        _ -> concatenated_product(N, I+1, Max, NewAcc)
    end.
    
%is it a permutation of the 1-9 digits
is_pandigital(X) ->
    digits(X, []) =:= [1,2,3,4,5,6,7,8,9].

%returns the digits of a number as a list
digits(0, Acc) ->
    lists:sort(Acc);
digits(X, Acc) ->
    digits(X div 10, [X rem 10|Acc]).


pow10(X, Acc) when X < 10 ->
    Acc;
pow10(X, Acc) ->
    pow10(X div 10, Acc*10).
